package chapter2;

public class SmallSum {
    public static int process(int[] arr,int l,int r){
        if (l==r){
            return 0;
        }
        int mid = l + ((r-l)>>1);
        return process(arr,l,mid) + process(arr,mid+1,r) + merge(arr,l,mid,r);
    }
    public static int merge(int[] arr,int l,int mid,int r){
        int[] help = new int[r-l+1];
        int i =0;
        int sum=0;
        int left_pointer = l;
        int right_pointer = mid+1;
        while (left_pointer <= mid && right_pointer <= r){
            if (arr[left_pointer] < arr[right_pointer]){
                sum += arr[left_pointer]*(r-right_pointer+1);//先判断后排序
                help[i++] = arr[left_pointer++];

            }else{
                help[i++] = arr[right_pointer++];
            }
        }
        while (left_pointer <= mid){
            help[i++] = arr[left_pointer++];
        }
        while (right_pointer <= r){
            help[i++] = arr[right_pointer++];
        }
        for (int j = 0; j < r-l+1; j++) {
            arr[l+j] = help[j];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {1,3,5};
        System.out.println(process(arr, 0, arr.length - 1));
    }
}
